A trie (from the middle four letters of “retrieve”) is a hierarchical data storage structure for storing and retrieving information items. The stored items consist of an address-prefix (normally referred to as just “prefix”) plus data, where the prefix is employed as a tag for identifying the associated data (i.e., the prefix is similar to a file name, and the data is like the file contents). An item's data is retrieved by searching for the associated prefix with the value of the prefix as the search key (similar to finding a file based on knowledge of the filename and then retrieving the file's contents).
Prefixes in trie structures are hierarchically organized according to numeric value into an easily searchable tree structure. In single bit (or unibit) tries, each bit within the prefix defines which branch is to be followed at the corresponding level of the data structure hierarchy, and is constrained in access speed by the need to read each bit. Multi-bit (or expanded) tries use several bits, referred to as the stride length, at a time during searching to improve access speed, requiring that prefixes of a size less than an exact multiple of the stride length be expanded to the next stride length boundary.
Bitmapped multi-bit tries employ bitmaps to eliminate redundant information, and thus reduce the amount of memory and operations required to hold and update the trie. While compact and easily modifiable, further reduction in the amount of memory required to represent a trie holding a given number of prefixes are possible.
There is, therefore, a need in the art for improving bitmapped multi-bit tries and the use of such structures.